package offer.offer01;


public class S10斐波那契数列 {
    /**
     * 直接用递归做, 相当于每一次计算结果都被浪费了, 比如fib(100)要计算fib(99)
     * 和fib(98), 但是fib(99)也需要计算fib(98), 需要巨大的开销但是被计算了两次。
     */
    public int fib(int n) {
        if(n<2) return n==1? 1:0;
        return(fib(n-1) + fib(n - 2));
    }
    /**
     * 使用一个私有数组来记录每一次计算的结果, int类型4个byte, 最大可以表示2^31-1
     * 其实这个数组可以放在fib函数内, 不用私有的
     */
    private int[] fibList = new int[101];
    public int fib2(int n) {
        fibList[0] = 0;
        fibList[1] = 1;
        for(int i = 2; i <= n; i++) {
            fibList[i] = (fibList[i-1] + fibList[i-2])%1000000007;
        }
        return fibList[n];
    }
    /**
     * 一种奇特的fib数列的迭代方式, 也可以多一个中间变量, 其实没有区别
     */
    public int fib3(int n) {
        if(n < 2) return n;
        int a = 1, b = 0;
        for(int i = 2; i <= n; i++) {
            a += b;
            b = a - b;
            a %= 1000000007;
        }
        return a;
    }
}
